package com.ly.algorithm.leetcode.linked;

/**
 * @Classname Problem61
 * @Description
 * 给定一个链表，旋转链表，将链表每个节点向右移动 k 个位置，其中 k 是非负数。
 *
 * 示例 1:
 *
 * 输入: 1->2->3->4->5->NULL, k = 2
 * 输出: 4->5->1->2->3->NULL
 * 解释:
 * 向右旋转 1 步: 5->1->2->3->4->NULL
 * 向右旋转 2 步: 4->5->1->2->3->NULL
 * 示例 2:
 *
 * 输入: 0->1->2->NULL, k = 4
 * 输出: 2->0->1->NULL
 * 解释:
 * 向右旋转 1 步: 2->0->1->NULL
 * 向右旋转 2 步: 1->2->0->NULL
 * 向右旋转 3 步: 0->1->2->NULL
 * 向右旋转 4 步: 2->0->1->NULL
 *
 * @Date 2020/12/15 18:58
 * @Author 冷心影翼
 */
public class Problem61 {

	public static void main(String[] args) {
		Solution61 solution61 = new Solution61();
		ListNode listNode = new ListNode(1);
		listNode.next = new ListNode(2);
		listNode.next.next = new ListNode(3);
		listNode.next.next.next = new ListNode(4);
//		listNode.next.next.next.next = new ListNode(5);
		solution61.rotateRight(listNode,0).printRes();
	}
}



/*
 * 输入: 1->2->3->4->5->NULL, k = 2
 * 输出: 4->5->1->2->3->NULL
 * 解释:
 * 向右旋转 1 步: 5->1->2->3->4->NULL
 * 向右旋转 2 步: 4->5->1->2->3->NULL
 */
class Solution61 {
	public ListNode rotateRight(ListNode head, int k) {
		if(head == null)
			return null;
		int size = 0;
		ListNode cur = head;
		while (cur!=null) {
			cur = cur.next;
			size++;
		}
		int n = size - k%size;
		cur = head;
		while (n>1) {
			cur = cur.next;
			n--;
		}
		if(cur.next == null)
			return head;
		ListNode newHead = cur.next;
		ListNode p = newHead;
		while (p.next!=null) {
			p = p.next;
		}
		p.next = head;
		cur.next = null;
		return newHead;
	}
}